public class Test1 {
    //leectode 712 两个字符串的最小ASCII删除和
    public int minimumDeleteSum(String s1, String s2) {
        //看到这个题首先想到的状态定义就是dp[i][j]表示s1字符串[0,i]之间的子串和s2字符串[0,j]之间的子串
        //是两个字符串相等的删除的最小的ASCII码值，这样虽然可以做，但是较为复杂
        //所以我们换个思路，正难则反，他要找的是使字符串相等的删除的字符的最小的ASCII值，所以我们可以定义
        //dp[i][j]为s1字符串[0,i]之间的子串和s2字符串[0,j]之间的子串中字符组成的最长的子串
        //所以状态转移方程：根据最近的一个状态来推，也就是s1.charAt(i)和s2.charAt(j)的情况
        //当s1.charAt(i) == s2.charAt(j),dp[i][j] = dp[i-1][j-1] + s1.charAt(i)
        //当s1.charAt(i) != s2.charAt(j)时,那么s1字符串[0,i]之间的子串和s2字符串[0,j]之间的相同的子串
        //一定不可能以s1[i]和s[j]结尾，那么这时候有三种情况：s1字符串[0,i]之间的子串和s2字符串[0,j]之间最长的相同的
        //子串以s1[i]结尾；或者以s2[j]结尾；或者都不以这两个字符结尾
        //对应这三种情况的状态转移方程是：dp[i][j] = dp[i][j-1],dp[i][j] = dp[i-1][j],dp[i][j] = dp[i-1][j-1]
        //前两种情况包括了第三种情况，所以可以省略
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        //初始化，当s1串或者s2串为空串的时候，无最长子串
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + s1.charAt(i - 1);
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        int sum = 0;
        for (char s : s1.toCharArray()) sum += s;
        for (char s : s2.toCharArray()) sum += s;
        return sum - 2 * dp[m][n];
    }
}
